This invention relates to logic circuits and in particular to an improved bifurcation circuit for use with event logic circuits and combinatorial logic.
FIFO pipelines are widely used in the computer, telecommunication, and related fields to handle data elements. A FIFO pipeline includes N stages where N is two or more. Data elements enter at one end of the pipeline, and in a succession of steps, progress from one stage to the next. Eventually, the data elements exit the pipeline at the last or Nth stage, in the same order in which the data elements entered the FIFO (i.e., first-in first-out). FIFOs may be either synchronous or asynchronous. In a synchronous FIFO, the stages operate within a rhythm imposed from an outside source, such as a clock. Each task that is performed at a particular stage must be completed within the clock period. With asynchronous FIFOs, each stage operates at its own pace.
The general functionality of asynchronous FIFOs is well known. See, for example, U.S. Pat. No. 5,838,933, issued to Molnar et al. and assigned to the assignee of the present application, which is incorporated herein by reference for all purposes.
One event driven FIFO circuit is known as an Asynchronous Symmetric Persistent Pulse Protocol (asP*) FIFO. Such a FIFO is depicted in FIG. 1. The FIFO 100 can be thought of as a sequence of xe2x80x9cplacesxe2x80x9d 110(a)-(e) joined by xe2x80x9cpathsxe2x80x9d 120(a)-(d). Each place 110 has a predecessor path and a successor path. Similarly, each path 120 has a predecessor place and a successor place. For example, place 110(b) has predecessor path 120(a) and successor path 120(b). Path 120(a) has predecessor place 110(a) and successor place 110(b). Places 110(a)-(e) and paths 120(a)-(d) follow simple rules. Each place 110(a)-(e) as two states, FULL and EMPTY. Each place 110(a)-(e) reports its state to its predecessor and successor paths. Each path 120(a)-(d) acts when it detects that its predecessor place is FULL and its successor place is EMPTY. When a path, such as path 120(a), acts, it transmits the data from its predecessor place to its successor place and changes the states of both places, i.e., place 110(a) becomes EMPTY and place 110(b) becomes FULL.
One can think of the places 110 as having a data part and a control part. The data part holds the data value copied from the previous place. The control part contains the state FULL or EMPTY. The control part acts like a xe2x80x9cset-resetxe2x80x9d (SR) latch or flip-flop. The paths on either side of a given place drive the set and reset inputs of the control flip-flop to cause the place to become FULL or EMPTY as the protocol demands.
In a pseudo-dynamic asP* protocol, the state of a place, such as 110(b) is represented by the charge (or voltage) on a wire 111 connected to paths 120(a) and 120(b). A small xe2x80x9ckeeperxe2x80x9d 112, typically just a pair of cross-tied inverters, retains the charge on wire 111 when it is not otherwise driven. The electrical capacitance of the wire 111 and the drive of the keeper 112 together form a control flip-flop.
In a dynamic asP* FIFO, such as that illustrated in FIG. 1, the places 110(a)-(e) alternate in type. This alternation arranges the meaning of the HI and LO states of the control flip-flops in the places 110 to simplify the circuits in the paths 120 as much as possible. In some places, such as place 110(b) a HI keeper voltage means FULL, but in others, such as place 110(c), a LO keeper voltage means FULL. Because the places 110(a)-(e) alternate in type paths, 120(a)-(d) will detect the FULL-EMPTY condition as either two HI signals or two LO signals, depending on where the path is in the sequence. There are also two types of paths, one like path 120(b) responding to a HIxe2x80x94HI condition of its adjacent places, the other like path 120(c) responding to LOxe2x80x94LO. When a path detects that it should act, it creates a pulse on its output. The pulse transmits the data forward to the successor place and toggles the control state in both the successor and predecessor places. One type of path produces a HI pulse when it acts, the other a LO. These pulses are of the right sense to toggle the control state of the adjacent places appropriately.
Several logic operations that commonly employ FIFO circuits. One such operation is a xe2x80x9cbifurcationxe2x80x9d. A bifurcation describes both the branching of one stream of data elements into two streams and the joining of two streams of data elements into one stream. Since branch and join operations are very similar, the term bifurcation was coined to cover both.
As with many circuits employing FIFOs not previously introduced, speed and chip area are at a premium.
This invention provides an improved bifurcation circuit, for high-speed and low component count uses as well as improvements in speed and chip area usage. The various embodiments of the present invention provide bifurcation circuits employing a dynamic asP* protocol. The bifurcator circuit generally employs return to zero logic. The bifurcator circuit generally comprises an asynchronous pulse (asP*) control FIFO containing a plurality of places and paths, two subordinate asP* FIFOs, and a bifurcation path coupled to all three FIFOs. The bifurcator circuit further comprises a chain of data latches coupled to all three FIFOs at the bifurcation path. A control value carried in the control FIFO determines which of the subordinate FIFOs exchanges data with the control FIFO. The bifurcation path moves the data value from a predecessor place to a successor place when the predecessor place is FULL and the successor place is EMPTY.
There are three key parts of the dynamic asP* implementation of the bifurcator circuits described here. First, each place in the asynchronous FIFOs in the bifurcator circuits contains a set reset flip-flop in which the state of each place is held by a single wire and stabilized by a small keeper. Second, a single N-type or P-type transistor sets or resets the state of the place. Thus the last of the logic gates in the minimum loop is a single transistor and not a complete gate. This makes the circuit operate very much faster than the earlier asP* implementations. Third, the same pulse that changes the state of the control flip-flops also makes the data latches momentarily transparent. Previous asP* designs have mainly used the state of the control flip-flops to condition the data latches.
The bifurcator circuit is generally capable of a branch operation wherein, depending upon the control value, the bifurcation path moves the data value from a predecessor place in the control FIFO to a successor place is one of the two subordinate FIFOs. Similarly, the bifurcator circuit of the present invention is capable of a join operation wherein the bifurcation path moves a data value from a predecessor place in one of the two subordinate FIFOs to a successor place in the control FIFO depending on the data value. Alternative embodiments of the bifurcator circuit are implemented as either branch or join circuits
In the circuits of the various embodiments of the present invention, each of the places generally contains a keeper coupled at a node to an N-type transistor and a P-type transistor. Each of the paths generally includes a NAND gate coupled to an inverter. Each of the data latches generally includes a pair of transistors coupled to a keeper. The output of the path is coupled a gate electrode of at least one of the transistors in the place. The path produces an output pulse that resets the state of the place. The same output pulse is also coupled to the transistors in a data latch to move the data to the next latch in the chain.
The bifurcator circuits described herein provide for rapidly branching or joining of data streams depending on the binary values of data and control signals. Such circuits exhibit simple design, low power consumption low transistor count and easy integration into existing applications.